package edu.ua.jCompare;


import java.util.ArrayList;
import java.util.Hashtable;

public class Diff {

	private DiffData dataA;
	private DiffData dataB;
	
	private String[] aLines;
	private String[] bLines;
	
	public Diff(String textA, String textB){
		this(textA, textB, false);
	}

	public Diff(String textA, String textB, boolean ignoreCase) {
		this(TextProcessor.splitByPuncSpace(textA),TextProcessor.splitByPuncSpace(textB), ignoreCase );
		
	}
	
	public Diff(String[] LinesA, String[] linesB, boolean ignoreCase){
		aLines = LinesA;
		bLines = linesB;
		
		Hashtable h = new Hashtable(aLines.length + bLines.length);

		// The A-Version of the data (original data) to be compared.
		dataA = new DiffData(diffCodes(aLines, h, ignoreCase));

		// The B-Version of the data (modified data) to be compared.
		dataB = new DiffData(diffCodes(bLines, h, ignoreCase));

		h = null; // free up hashtable memory (maybe)
		getDiff();
	}
	
	public void getDiff(){
		int MAX = dataA.Length + dataB.Length + 1;
		// / vector for the (0,0) to (x,y) search
		int[] downVector = new int[2 * MAX + 2];
		// / vector for the (u,v) to (N,M) search
		int[] upVector = new int[2 * MAX + 2];

		LCS(dataA, 0, dataA.Length, dataB, 0, dataB.Length, downVector,
				upVector);
		
	}
	
	public int getLCSCount() {
		int lcsCount = 0;
		if (dataA.Length < dataB.Length) {
			for (int i = 0; i < dataA.Length; i++) {
				if (!dataA.modified[i])
					lcsCount++;
			}
		} else {
			for (int i = 0; i < dataB.Length; i++) {
				if (!dataB.modified[i])
					lcsCount++;
			}
		}
		return lcsCount;

	}

	public int getDiffCount() {
		int diffCount = 0;
		for (int i = 0; i < dataA.Length; i++) {
			if (dataA.modified[i]) {
				diffCount++;
			}
		}

		for (int i = 0; i < dataB.Length; i++) {
			if (dataB.modified[i]) {
				diffCount++;
			}

		}
		return diffCount;

	}
	
	public int getRemovedCount(){
		int removedCount = 0;
		for (int i = 0; i < dataA.Length; i++) {
			if (dataA.modified[i]) {
				removedCount++;
			}
		}

		
		return removedCount;
	}
	
	public int getInsertedCount(){
		int insertedCount = 0;
		for (int i = 0; i < dataB.Length; i++) {
			if (dataB.modified[i]) {
				insertedCount++;
			}
		}
		return insertedCount;
	}
	
	public void getDiffOutput(Renderer r){
		int indexA = 0;
		int indexB = 0;

		ArrayList<String> matchedLines = new ArrayList<String>();
		ArrayList<String> deletedLines = new ArrayList<String>();
		ArrayList<String> insertedLines = new ArrayList<String>();
		
		r.initialize();
		
		while (indexA < dataA.Length || indexB < dataB.Length) {
			// equal lines
			while ((indexA < dataA.Length) && (!dataA.modified[indexA])
					&& (indexB < dataB.Length) && (!dataB.modified[indexB])) {
				matchedLines.add(aLines[indexA]);
				indexA++;
				indexB++;
			}
			if (matchedLines.size() > 0) {
				r.renderMatches(matchedLines);
				matchedLines = new ArrayList<String>();
			}
			// deleted lines
			while (indexA < dataA.Length
					&& (indexB >= dataB.Length || dataA.modified[indexA])) {
				deletedLines.add(aLines[indexA]);
				indexA++;
			}
			if (deletedLines.size() > 0) {
				r.renderDeletes(deletedLines);
				deletedLines = new ArrayList<String>();
			}
			// inserted lines
			while (indexB < dataB.Length
					&& (indexA >= dataA.Length || dataB.modified[indexB])) {
				insertedLines.add(bLines[indexB]);
				indexB++;
			}
			if (insertedLines.size() > 0) {
				r.renderInserts(insertedLines);
				insertedLines = new ArrayList<String>();
			}

		} // while
		r.finalize();
	}
	
	
	// This method converts all text lines of the text into unique numbers
	// so further work can work only with simple numbers.
	private static int[] diffCodes(String[] lines, Hashtable h,
			 boolean ignoreCase) {
		// get all codes of the text
		
		int[] codes;
		int lastUsedCode = h.size();
		String s;

		codes = new int[lines.length];

		for (int i = 0; i < lines.length; ++i) {
			s = lines[i];
			
			if (ignoreCase)
				s = s.toLowerCase();

			Object aCode = h.get(s);
			if (aCode == null) {
				lastUsedCode++;
				h.remove(s);
				h.put(s, lastUsedCode);
				codes[i] = lastUsedCode;
			} else {
				codes[i] = (Integer) aCode;
			} // if
		} // for
		return (codes);
	} // DiffCodes

	
	// This is the algorithm for finding the Shortest Middle Snake (SMS).
	// "DownVector" is a vector for the (0,0) to (x,y) search. 
	// Passed as a parameter for speed reasons.
	// "UpVector" similarly is a vector for the (u,v) to (N,M) search. 
	// the output is a MiddleSnakeData record containing x,y and u,v</returns>
	private static SMSRD SMS(DiffData dataA, int lowerA, int upperA,
			DiffData dataB, int lowerB, int upperB, int[] downVector,
			int[] upVector) {

		SMSRD ret = new SMSRD();
		int max = dataA.Length + dataB.Length + 1;

		int downK = lowerA - lowerB; // the k-line to start the forward search
		int upK = upperA - upperB; // the k-line to start the reverse search

		int delta = (upperA - lowerA) - (upperB - lowerB);
		boolean oddDelta = (delta & 1) != 0;

		// The vectors in the publication accepts negative indexes. the vectors
		// implemented here are 0-based
		// and are access using a specific offset: upOffset upVector and
		// downOffset for downVektor
		int downOffset = max - downK;
		int upOffset = max - upK;

		int maxD = ((upperA - lowerA + upperB - lowerB) / 2) + 1;

		// init vectors
		downVector[downOffset + downK + 1] = lowerA;
		upVector[upOffset + upK - 1] = upperA;

		for (int d = 0; d <= maxD; d++) {

			// Extend the forward path.
			for (int k = downK - d; k <= downK + d; k += 2) {
			
				// find the only or better starting point
				int x, y;
				if (k == downK - d) {
					x = downVector[downOffset + k + 1]; // down
				} else {
					x = downVector[downOffset + k - 1] + 1; // a step to the
															// right
					if ((k < downK + d)
							&& (downVector[downOffset + k + 1] >= x))
						x = downVector[downOffset + k + 1]; // down
				}
				y = x - k;

				// find the end of the furthest reaching forward D-path in
				// diagonal k.
				while ((x < upperA) && (y < upperB)
						&& (dataA.data[x] == dataB.data[y])) {
					x++;
					y++;
				}
				downVector[downOffset + k] = x;

				// overlap ?
				if (oddDelta && (upK - d < k) && (k < upK + d)) {
					if (upVector[upOffset + k] <= downVector[downOffset + k]) {
						ret.x = downVector[downOffset + k];
						ret.y = downVector[downOffset + k] - k;
						return (ret);
					} // if
				} // if

			} // for k

			// Extend the reverse path.
			for (int k = upK - d; k <= upK + d; k += 2) {

				// find the only or better starting point
				int x, y;
				if (k == upK + d) {
					x = upVector[upOffset + k - 1]; // up
				} else {
					x = upVector[upOffset + k + 1] - 1; // left
					if ((k > upK - d) && (upVector[upOffset + k - 1] < x))
						x = upVector[upOffset + k - 1]; // up
				} // if
				y = x - k;

				while ((x > lowerA) && (y > lowerB)
						&& (dataA.data[x - 1] == dataB.data[y - 1])) {
					x--;
					y--; // diagonal
				}
				upVector[upOffset + k] = x;

				// overlap ?
				if (!oddDelta && (downK - d <= k) && (k <= downK + d)) {
					if (upVector[upOffset + k] <= downVector[downOffset + k]) {
						ret.x = downVector[downOffset + k];
						ret.y = downVector[downOffset + k] - k;
						return (ret);
					} // if
				} // if

			} // for k

		} // for D

		System.out.println("the algorithm should never come here.");
		return null;
	} 

	// This is the divide-and-conquer implementation of the longest common-subsequence (LCS)
	// The published algorithm passes recursively parts of the A and B sequences.
	// To avoid copying these arrays the lower and upper bounds are passed
	// while the sequences stay constant.
	private static void LCS(DiffData dataA, int lowerA, int upperA,
			DiffData dataB, int lowerB, int upperB, int[] downVector,
			int[] upVector) {
		
		// Fast walkthrough equal lines at the start
		while (lowerA < upperA && lowerB < upperB
				&& dataA.data[lowerA] == dataB.data[lowerB]) {
			lowerA++;
			lowerB++;
		}

		// Fast walkthrough equal lines at the end
		while (lowerA < upperA && lowerB < upperB
				&& dataA.data[upperA - 1] == dataB.data[upperB - 1]) {
			--upperA;
			--upperB;
		}

		if (lowerA == upperA) {
			// mark as inserted lines.
			while (lowerB < upperB)
				dataB.modified[lowerB++] = true;

		} else if (lowerB == upperB) {
			// mark as deleted lines.
			while (lowerA < upperA)
				dataA.modified[lowerA++] = true;

		} else {
			// Find the middle snake and length of an optimal path for A and B
			SMSRD smsrd = SMS(dataA, lowerA, upperA, dataB, lowerB, upperB,
					downVector, upVector);
			
			// The path is from LowerX to (x,y) and (x,y) to UpperX
			LCS(dataA, lowerA, smsrd.x, dataB, lowerB, smsrd.y, downVector,
					upVector);
			LCS(dataA, smsrd.x, upperA, dataB, smsrd.y, upperB, downVector,
					upVector);
		}
	} 
} 



